package 代码随想录_动态规划.子序列问题.回文;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zx
 * @create 2023-01-18 22:02
 * 这题属于回溯,但是是回文串相关的
 */
public class 分割回文串_131 {
    List<List<String>> res = new ArrayList<>();
    LinkedList<String> list = new LinkedList<>();
    public List<List<String>> partition(String s) {
        dfs(s,0);
        return res;
    }
    private void dfs(String s, int startIndex){
        if(startIndex >= s.length()){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = startIndex;i < s.length();i++){
            if(!isHuiWen(s,startIndex,i)){
                continue;
            }
            String str = s.substring(startIndex,i + 1);
            list.add(str);
            dfs(s,i + 1);
            list.removeLast();
        }
    }
    //判断是否是回文串
    private boolean isHuiWen(String s, int start, int end){
        for(int i = start,j = end;i < j;i++,j--){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}
